from typing import List


class Solution:
    def insert(self, pend, val):
        new = []
        last = False
        for pos in range(len(pend)+1):
            _list = pend[:]
            if last and pos > 0 and pend[pos-1] == val:
                continue
            _list.insert(pos, val)
            if pos < len(pend) and pend[pos] == val:
                last = True
            else:
                last = False
            new.append(_list)
        return new

    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        start = [[nums[0]]]
        remind = nums[1:]
        p = 0
        last = None
        while p < len(remind):
            temp_start = []
            for e in start:
                temp = self.insert(e, remind[p])
                temp_start += temp
            start = temp_start
            p+=1

        return start

if __name__ == '__main__':
    print("ERROR: 全排列II: 给定一个包含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以按任意顺序返回答案。\n https://leetcode.cn/problems/permutations/\n")
    print("\n这次就仔细思考了，发现用逐个位置插入\n\n")
    test =[
            [1,1,5,5]
        ]
    for v in test:
        print('---', v)
        ret = Solution().permuteUnique(v)
        print(ret)